/**
  * collide() returns true if the set of triangles contained within the OBBTrees intersect
  * between the OBBTrees; otherwise, false is returned.
  * If a maxDepth is specified, collide() will return true if the maximum depth is reached,
  * even though collide() has not determined whether there is a collision or not. A negative 
  * maxDepth is equivalent to having no maximum depth.
  *
  * @param (OBBTree<TYPENAME>&) obbtreeA
  * @param (OBBTree<TYPENAME>&) obbtreeB
  * @param (int) maxDepth
  * @return bool
  */
 template <typename TYPENAME>
 inline CollisionInfo<TYPENAME> collideE( OBBTree<TYPENAME>& obbtreeA, OBBTree<TYPENAME>& obbtreeB, int maxDepth )
 {
    if ( maxDepth > 0 )
        return collideE( obbtreeA, obbtreeB, maxDepth, maxDepth );
    else if ( maxDepth == 0 )
    {
        if ( collide( obbtreeA.obb, obbtreeB.obb ) )
            return CollisionInfo<TYPENAME>( 1, 0, 0, obbtreeA.obb, obbtreeB.obb, GL_Triangle<TYPENAME>(0,0,0,0,0,0,0,0,0), GL_Triangle<TYPENAME>(0,0,0,0,0,0,0,0,0) );
        else
            return CollisionInfo<TYPENAME>( -1, 0, 0, obbtreeA.obb, obbtreeB.obb, GL_Triangle<TYPENAME>(0,0,0,0,0,0,0,0,0), GL_Triangle<TYPENAME>(0,0,0,0,0,0,0,0,0) );
    }
    else // maxDepth < 0
        return collideE( obbtreeA, obbtreeB );
 }
 
 /**
  * collide() returns true if the set of triangles contained within the OBBTrees intersect
  * between the OBBTrees; otherwise, false is returned.
  * If a maxDepth is specified, collide() will determine if the two OBBTrees collide based
  * on the OBBs on the depth level when the maximum depth is reached. Each maxDepth is 
  * assumed to be greater than or equal to zero.
  *
  * @param (OBBTree<TYPENAME>&) obbtreeA
  * @param (OBBTree<TYPENAME>&) obbtreeB
  * @param (size_t) maxDepthA
  * @param (size_t) maxDepthB
  * @return CollisionInfo<TYPENAME>
  */
 template <typename TYPENAME>
 inline CollisionInfo<TYPENAME> collideE( OBBTree<TYPENAME>& obbtreeA, OBBTree<TYPENAME>& obbtreeB )
 {
    if ( collide( obbtreeA.obb, obbtreeB.obb ) )
    {
        if ( obbtreeB.leftChild() ) // if obbtreeB has a left child
        {
            if ( obbtreeB.rightChild() ) // if obbtreeB has a left and right child
            {
                CollisionInfo<TYPENAME> c1 ( collideE( obbtreeA, *obbtreeB.leftChild() ) );
                CollisionInfo<TYPENAME> c2 ( collideE( obbtreeA, *obbtreeB.rightChild() ) );
                return MAX( c1, c2 );
            }
            else // if obbtreeB only has a left child
            {
                return collideE( obbtreeA, *obbtreeB.leftChild() );
            }
        }
        else if ( obbtreeB.rightChild() ) // if obbtreeB only has a right child
        {
            return collideE( obbtreeA, *obbtreeB.rightChild() );
        }
        else // if obbtreeB has no children
        {
            if ( obbtreeA.leftChild() ) // if obbtreeA has a left child
            {
                if ( obbtreeA.rightChild() ) // if obbtreeA has a left and right child
                {
                    CollisionInfo<TYPENAME> c1 ( collideE( *obbtreeA.leftChild(), obbtreeB ) );
                    CollisionInfo<TYPENAME> c2 ( collideE( *obbtreeA.rightChild(), obbtreeB ) );
                    return MAX( c1, c2 );
                }
                else // if obbtreeA only has a left child
                {
                    return collideE( *obbtreeA.leftChild(), obbtreeB );
                }
            }
            else if ( obbtreeA.rightChild() ) // if obbtreeA only has a right child
            {
                return collideE( *obbtreeA.rightChild(), obbtreeB );
            }
            else // neither obbtreeA nor obbtreeB has a child
            {
                // Currently, there will always be exactly one triangle in obbtreeA and obbtreeB, so there is no
                // reason for having the do-while-loop.
                
                // if any triangle from OBBTree A collides with any triangle from OBBTree B, then return true;
                // otherwise, return false.
                size_t triangle_index_A( obbtreeA.triangle_Ptrs.size() );
                if ( triangle_index_A > 0 )
                {
                    do
                    {
                        --triangle_index_A;
                        const GL_Triangle<TYPENAME>& triangleA( *obbtreeA.triangle_Ptrs[ triangle_index_A ] );
                        
                        size_t triangle_index_B( obbtreeB.triangle_Ptrs.size() );
                        if ( triangle_index_B > 0 )
                        {
                            do
                            {
                                --triangle_index_B;
                                const GL_Triangle<TYPENAME>& triangleB( *obbtreeB.triangle_Ptrs[ triangle_index_B ] );

                                if ( collide( triangleA, triangleB ) )
                                    return CollisionInfo<TYPENAME>( 1, 0, 0, obbtreeA.obb, obbtreeB.obb, triangleA, triangleB );
                            } while ( triangle_index_B > 0 );
                        }
                        else
                            break;
                    } while ( triangle_index_A > 0 );
                }
            }
        }
    }
    
    return CollisionInfo<TYPENAME>( -1, 0, 0, obbtreeA.obb, obbtreeB.obb, GL_Triangle<TYPENAME>(0,0,0,0,0,0,0,0,0), GL_Triangle<TYPENAME>(0,0,0,0,0,0,0,0,0) );
 }
 
 #if 0
 /**
  * collide() returns true if the set of triangles contained within the OBBTrees intersect
  * between the OBBTrees; otherwise, false is returned.
  * If a maxDepth is specified, collide() will determine if the two OBBTrees collide based
  * on the OBBs on the depth level when the maximum depth is reached. Each maxDepth is 
  * assumed to be greater than or equal to zero.
  *
  * @param (OBBTree<TYPENAME>&) obbtreeA
  * @param (OBBTree<TYPENAME>&) obbtreeB
  * @param (size_t) maxDepthA
  * @param (size_t) maxDepthB
  * @return CollisionInfo<TYPENAME>
  */
 template <typename TYPENAME>
 inline CollisionInfo<TYPENAME> collideE( OBBTree<TYPENAME>& obbtreeA, OBBTree<TYPENAME>& obbtreeB, size_t maxDepthA, size_t maxDepthB )
 {
    if ( maxDepthA == 0 || !obbtreeA.hasChild()  )
    {
        if ( maxDepthB == 0 || !obbtreeB.hasChild() )
        {
            bool test( collide( obbtreeA.obb, obbtreeB.obb ) );
            if ( test )
                return CollisionInfo<TYPENAME>( 1, 0, 0, obbtreeA.obb, obbtreeB.obb );
            else
                return CollisionInfo<TYPENAME>( -1, 0, 0, obbtreeA.obb, obbtreeB.obb );
        }
        else
        {
            return collideE( obbtreeB, obbtreeA, maxDepthB, maxDepthA );
        }
    }
    
    if ( collide( obbtreeA.obb, obbtreeB.obb ) )
    {
        if ( obbtreeB.leftChild() ) // if obbtreeB has a left child
        {
            if ( obbtreeB.rightChild() ) // if obbtreeB has a left and right child
            {
                CollisionInfo<TYPENAME> c1 ( collideE( obbtreeA, *obbtreeB.leftChild(), maxDepthA, --maxDepthB ) );
                CollisionInfo<TYPENAME> c2 ( collideE( obbtreeA, *obbtreeB.rightChild(), maxDepthA, maxDepthB ) );
                return MAX( c1, c2 );
            }
            else // if obbtreeB only has a left child
            {
                return collideE( obbtreeA, *obbtreeB.leftChild(), maxDepthA, --maxDepthB );
            }
        }
        else if ( obbtreeB.rightChild() ) // if obbtreeB only has a right child
        {
            return collideE( obbtreeA, *obbtreeB.rightChild(), maxDepthA, --maxDepthB );
        }
        else // if obbtreeB has no children
        {
            if ( obbtreeA.leftChild() ) // if obbtreeA has a left child
            {
                if ( obbtreeA.rightChild() ) // if obbtreeA has a left and right child
                {
                    CollisionInfo<TYPENAME> c1 ( collideE( obbtreeB, *obbtreeA.leftChild(), maxDepthB, --maxDepthA ) );
                    CollisionInfo<TYPENAME> c2 ( collideE( obbtreeB, *obbtreeA.rightChild(), maxDepthB, maxDepthA ) );
                    return MAX( c1, c2 );
                }
                else // if obbtreeA only has a left child
                {
                    return collideE( obbtreeB, *obbtreeA.leftChild(), maxDepthB, --maxDepthA );
                }
            }
            else if ( obbtreeA.rightChild() ) // if obbtreeA only has a right child
            {
                return collideE( obbtreeB, *obbtreeA.rightChild(), maxDepthB, --maxDepthA );
            }
            else // neither obbtreeA nor obbtreeB has a child
            {
            #if 0
                printf("Error: This should never be reached (OBBTree.h)\n");
                // Currently, there will always be exactly one triangle in obbtreeA and obbtreeB, so there is no
                // reason for having the do-while-loop.
                
                // if any triangle from OBBTree A collides with any triangle from OBBTree B, then return true;
                // otherwise, return false.
                size_t triangle_index_A( obbtreeA.triangle_Ptrs.size() );
                if ( triangle_index_A > 0 )
                {
                    do
                    {
                        --triangle_index_A;
                        const GL_Triangle<TYPENAME>& triangleA( *obbtreeA.triangle_Ptrs[ triangle_index_A ] );
                        
                        size_t triangle_index_B( obbtreeB.triangle_Ptrs.size() );
                        if ( triangle_index_B > 0 )
                        {
                            do
                            {
                                --triangle_index_B;
                                const GL_Triangle<TYPENAME>& triangleB( *obbtreeB.triangle_Ptrs[ triangle_index_B ] );

                                if ( collide( triangleA, triangleB ) )
                                    return true;
                            } while ( triangle_index_B > 0 );
                        }
                        else
                            break;
                    } while ( triangle_index_A > 0 );
                }
            #endif // #if 0
            }
        }
    }
    
    return CollisionInfo<TYPENAME>( -1, 0, 0, obbtreeA.obb, obbtreeB.obb );
 }
 #endif // #if 0
 
 /**
  * collide() returns true if the set of triangles contained within the OBBTrees intersect
  * between the OBBTrees; otherwise, false is returned.
  * If a maxDepth is specified, collide() will determine if the two OBBTrees collide based
  * on the OBBs on the depth level when the maximum depth is reached. Each maxDepth is 
  * assumed to be greater than or equal to zero.
  *
  * @param (OBBTree<TYPENAME>&) obbtreeA
  * @param (OBBTree<TYPENAME>&) obbtreeB
  * @param (size_t) maxDepthA
  * @param (size_t) maxDepthB
  * @return CollisionInfo<TYPENAME>
  */
 template <typename TYPENAME>
 inline CollisionInfo<TYPENAME> collideE( OBBTree<TYPENAME>& obbtreeA, OBBTree<TYPENAME>& obbtreeB, size_t maxDepthA, size_t maxDepthB )
 {
    if ( maxDepthA == 0 || !obbtreeA.hasChild()  )
    {
        if ( maxDepthB == 0 || !obbtreeB.hasChild() )
        {
            bool test( collide( obbtreeA.obb, obbtreeB.obb ) );
            if ( test )
                return CollisionInfo<TYPENAME>( 1, 0, 0, obbtreeA.obb, obbtreeB.obb, GL_Triangle<TYPENAME>(0,0,0,0,0,0,0,0,0), GL_Triangle<TYPENAME>(0,0,0,0,0,0,0,0,0) );
            else
                return CollisionInfo<TYPENAME>( -1, 0, 0, obbtreeA.obb, obbtreeB.obb, GL_Triangle<TYPENAME>(0,0,0,0,0,0,0,0,0), GL_Triangle<TYPENAME>(0,0,0,0,0,0,0,0,0) );
        }
    }
    
    if ( collide( obbtreeA.obb, obbtreeB.obb ) )
    {
        if ( obbtreeB.leftChild() ) // if obbtreeB has a left child
        {
            if ( obbtreeB.rightChild() ) // if obbtreeB has a left and right child
            {
                CollisionInfo<TYPENAME> c1 ( collideE( obbtreeA, *obbtreeB.leftChild(), maxDepthA, --maxDepthB ) );
                CollisionInfo<TYPENAME> c2 ( collideE( obbtreeA, *obbtreeB.rightChild(), maxDepthA, maxDepthB ) );
                return MAX( c1, c2 );
            }
            else // if obbtreeB only has a left child
            {
                return collideE( obbtreeA, *obbtreeB.leftChild(), maxDepthA, --maxDepthB );
            }
        }
        else if ( obbtreeB.rightChild() ) // if obbtreeB only has a right child
        {
            return collideE( obbtreeA, *obbtreeB.rightChild(), maxDepthA, --maxDepthB );
        }
        else // if obbtreeB has no children
        {
            if ( obbtreeA.leftChild() ) // if obbtreeA has a left child
            {
                if ( obbtreeA.rightChild() ) // if obbtreeA has a left and right child
                {
                    CollisionInfo<TYPENAME> c1 ( collideE( *obbtreeA.leftChild(), obbtreeB, --maxDepthA, maxDepthB ) );
                    CollisionInfo<TYPENAME> c2 ( collideE( *obbtreeA.rightChild(), obbtreeB, maxDepthA, maxDepthB ) );
                    return MAX( c1, c2 );
                }
                else // if obbtreeA only has a left child
                {
                    return collideE( *obbtreeA.leftChild(), obbtreeB, --maxDepthA, maxDepthB );
                }
            }
            else if ( obbtreeA.rightChild() ) // if obbtreeA only has a right child
            {
                return collideE( *obbtreeA.rightChild(), obbtreeB, --maxDepthA, maxDepthB );
            }
            else // neither obbtreeA nor obbtreeB has a child
            {
            #if 0
                printf("Error: This should never be reached (OBBTree.h)\n");
                // Currently, there will always be exactly one triangle in obbtreeA and obbtreeB, so there is no
                // reason for having the do-while-loop.
                
                // if any triangle from OBBTree A collides with any triangle from OBBTree B, then return true;
                // otherwise, return false.
                size_t triangle_index_A( obbtreeA.triangle_Ptrs.size() );
                if ( triangle_index_A > 0 )
                {
                    do
                    {
                        --triangle_index_A;
                        const GL_Triangle<TYPENAME>& triangleA( *obbtreeA.triangle_Ptrs[ triangle_index_A ] );
                        
                        size_t triangle_index_B( obbtreeB.triangle_Ptrs.size() );
                        if ( triangle_index_B > 0 )
                        {
                            do
                            {
                                --triangle_index_B;
                                const GL_Triangle<TYPENAME>& triangleB( *obbtreeB.triangle_Ptrs[ triangle_index_B ] );

                                if ( collide( triangleA, triangleB ) )
                                    return true;
                            } while ( triangle_index_B > 0 );
                        }
                        else
                            break;
                    } while ( triangle_index_A > 0 );
                }
            #endif // #if 0
            }
        }
    }
    
    return CollisionInfo<TYPENAME>( -1, 0, 0, obbtreeA.obb, obbtreeB.obb, GL_Triangle<TYPENAME>(0,0,0,0,0,0,0,0,0), GL_Triangle<TYPENAME>(0,0,0,0,0,0,0,0,0) );
 }
 
 #if 0
 /**
  * computeCollisionInfo() returns the CollisionInfo between the two specified OBBs, 
  * including the extent that the object need to move in the directions toward their 
  * previous positions to avoid the collision; if the extent returned is less than zero, 
  * then the two object are currently not intersecting. Zero is returned If the two 
  * OBBTrees are colliding, but the difference between the specified displacementA and 
  * displacementB is the zero vector (i.e. displacementA == displacementB), then the 
  * displacementA and displacementB will be modified to the normal vectors of the location 
  * of intersection on OBBTreeB and OBBTreeA, but in the reverse directions, respectively.
  * If a maxDepth is specified, collisionExtent() will return the extent when the maximum 
  * depth is reached for each specified OBBTree. Each maxDepth must be greater than or equal 
  * to zero.
  *
  * @param (OBBTree<TYPENAME>&) obbtreeA - OBBTree of object A
  * @param (OBBTree<TYPENAME>&) obbtreeB - OBBTree of object B
  * @param (size_t) maxDepthA
  * @param (size_t) maxDepthB
  * @param (Vector3<TYPENAME>) displacementA - the current position of object A minus the previous position of object A
  * @param (Vector3<TYPENAME>) displacementB - the current position of object B minus the previous position of object B
  * @return CollisionInfo<TYPENAME>
  */
 template <typename TYPENAME>
 inline CollisionInfo<TYPENAME> computeCollisionInfo( OBBTree<TYPENAME>& obbtreeA, OBBTree<TYPENAME>& obbtreeB, 
                      size_t maxDepthA, size_t maxDepthB, Vector3<TYPENAME> displacementA, Vector3<TYPENAME> displacementB )
 {
    if ( maxDepthA == 0 || !obbtreeA.hasChild()  )
    {
        if ( maxDepthB == 0 || !obbtreeB.hasChild() )
        {
            TYPENAME extent( collisionExtent( obbtreeA.obb, obbtreeB.obb, displacementA, displacementB ) );
            return CollisionInfo<TYPENAME>( extent, displacementA, displacementB, obbtreeA.obb, obbtreeB.obb );
        }
        /*else
        {
            return computeCollisionInfo( obbtreeB, obbtreeA, maxDepthB, maxDepthA );
        }*/
    }
    
    if ( collide( obbtreeA.obb, obbtreeB.obb ) )
    {
        if ( obbtreeB.leftChild() ) // if obbtreeB has a left child
        {
            if ( obbtreeB.rightChild() ) // if obbtreeB has a left and right child
            {
                CollisionInfo<TYPENAME> c1 ( computeCollisionInfo( obbtreeA, *obbtreeB.leftChild(), maxDepthA, --maxDepthB, displacementA, displacementB ) );
                CollisionInfo<TYPENAME> c2 ( computeCollisionInfo( obbtreeA, *obbtreeB.rightChild(), maxDepthA, maxDepthB, displacementA, displacementB ) );
                return MAX( c1, c2 );
            }
            else // if obbtreeB only has a left child
            {
                return computeCollisionInfo( obbtreeA, *obbtreeB.leftChild(), maxDepthA, --maxDepthB, displacementA, displacementB );
            }
        }
        else if ( obbtreeB.rightChild() ) // if obbtreeB only has a right child
        {
            return computeCollisionInfo( obbtreeA, *obbtreeB.rightChild(), maxDepthA, --maxDepthB, displacementA, displacementB );
        }
        else // if obbtreeB has no children
        {
            if ( obbtreeA.leftChild() ) // if obbtreeA has a left child
            {
                if ( obbtreeA.rightChild() ) // if obbtreeA has a left and right child
                {
                    CollisionInfo<TYPENAME> c1 ( computeCollisionInfo( *obbtreeA.leftChild(), obbtreeB, --maxDepthA, maxDepthB, displacementA, displacementB ) );
                    CollisionInfo<TYPENAME> c2 ( computeCollisionInfo( *obbtreeA.rightChild(), obbtreeB, maxDepthA, maxDepthB, displacementA, displacementB ) );
                    return MAX( c1, c2 );
                }
                else // if obbtreeA only has a left child
                {
                    return computeCollisionInfo( *obbtreeA.leftChild(), obbtreeB, --maxDepthA, maxDepthB, displacementA, displacementB );
                }
            }
            else if ( obbtreeA.rightChild() ) // if obbtreeA only has a right child
            {
                return computeCollisionInfo( *obbtreeA.rightChild(), obbtreeB, --maxDepthA, maxDepthB, displacementA, displacementB );
            }
            else // neither obbtreeA nor obbtreeB has a child
            {
                // Currently, there will always be exactly one triangle in obbtreeA and obbtreeB, so there is no
                // reason for having the do-while-loop.
                
                // if any triangle from OBBTree A collides with any triangle from OBBTree B, then return true;
                // otherwise, return false.
// WARNING: TEST
                printf("Error: This should never be reached (OBBTree.h)\n");
                //printf("Test OBBTree.h\n");
                //if ( obbtreeA.triangle_Ptrs.size() > 1 || obbtreeB.triangle_Ptrs.size() > 1 )
                    //printf( "Error: OBBTree.h - size of triangle_Ptrs > 1, when should be exactly 1\n" );
                
                TYPENAME extent( collisionExtent( *obbtreeA.triangle_Ptrs[ 0 ], *obbtreeB.triangle_Ptrs[ 0 ], 
                                                                                displacementA, displacementB ) );
                return CollisionInfo<TYPENAME>( extent, displacementA, displacementB, obbtreeA.obb, obbtreeB.obb );
            }
        }
    }
    
    return CollisionInfo<TYPENAME>( -1, displacementA, displacementB, obbtreeA.obb, obbtreeB.obb );
 }
#endif // #if 0